#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

int find_kth(int *array, int start, int end, int k) {
    int low = start;
    int high = end;
    int temp = array[low];
    
    if (start > end) {
        return -1;  // 无效区间
    }
    
    while (low < high) {
        // 将小于中数值的数移动到数组左边
        while ((low < high) && (array[high] >= temp)) {
            high--;
        }
        array[low] = array[high];
        
        // 将大于中数值的数移动到数组右边
        while ((low < high) && (array[low] <= temp)) {
            low++;
        }
        array[high] = array[low];
    }
    
    array[high] = temp;
    
    if (end - low + 1 == k) {
        return temp;
    } else if (end - low + 1 > k) {
        return find_kth(array, low + 1, end, k);
    } else {
        return find_kth(array, start, low - 1, k - (end - low + 1));
    }
}


// 辅助函数
void PrintArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void CopyArray(int src[], int dest[], int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

// 用于验证的排序函数
void SelectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

// 测试find_kth函数
void TestFindKth(int original[], int n, const char* testName) {
    printf("=== %s ===\n", testName);
    printf("原始数组: ");
    PrintArray(original, n);
    
    // 创建排序后的数组用于验证
    int sorted[n];
    CopyArray(original, sorted, n);
    SelectionSort(sorted, n);
    printf("排序后: ");
    PrintArray(sorted, n);
    
    printf("查找第k大元素测试:\n");
    printf("k值\t结果\t期望值\t正确性\n");
    printf("--------------------------------\n");
    
    // 测试所有k值
    for (int k = 1; k <= n; k++) {
        int test_array[n];
        CopyArray(original, test_array, n);
        
        int result = find_kth(test_array, 0, n - 1, k);
        int expected = sorted[n - k];  // 第k大元素

        printf("%d\t%d\t%d\t%s\n", 
               k, result, expected,
               (result == expected) ? "✓" : "✗");
    }
    printf("\n");
}

// 边界情况测试
void TestEdgeCases() {
    printf("=== 边界情况测试 ===\n");
    
    // 测试单个元素
    printf("测试1：单个元素\n");
    int single[] = {42};
    int test_single[1];
    CopyArray(single, test_single, 1);
    int result1 = find_kth(test_single, 0, 0, 1);
    printf("数组: [42], 第1大元素: %d %s\n", result1, (result1 == 42) ? "✓" : "✗");

    // 测试相同元素
    printf("\n测试2：相同元素\n");
    int same[] = {5, 5, 5, 5};
    int test_same[4];
    CopyArray(same, test_same, 4);
    int result2 = find_kth(test_same, 0, 3, 2);
    printf("数组: [5, 5, 5, 5], 第2大元素: %d %s\n", result2, (result2 == 5) ? "✓" : "✗");

    printf("\n");
}

// 主测试函数
void TestFindKthComprehensive() {
    printf("========== find_kth函数测试 ==========\n\n");
    
    // 测试用例1：一般情况
    int test1[] = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    int n1 = sizeof(test1) / sizeof(test1[0]);
    TestFindKth(test1, n1, "测试1：一般情况");
    
    // 测试用例2：已排序数组
    int test2[] = {1, 2, 3, 4, 5};
    int n2 = sizeof(test2) / sizeof(test2[0]);
    TestFindKth(test2, n2, "测试2：已排序数组");
    
    // 测试用例3：逆序数组
    int test3[] = {5, 4, 3, 2, 1};
    int n3 = sizeof(test3) / sizeof(test3[0]);
    TestFindKth(test3, n3, "测试3：逆序数组");
    
    // 测试用例4：重复元素
    int test4[] = {3, 1, 3, 3, 2, 3, 1};
    int n4 = sizeof(test4) / sizeof(test4[0]);
    TestFindKth(test4, n4, "测试4：重复元素");
    
    // 边界情况测试
    TestEdgeCases();
    
}

// 主函数
int main() {
    TestFindKthComprehensive();
    return 0;
}